package com.itheima.datastructure.demo1;

import java.util.BitSet;
/**
 * Sushu 类用于演示两种不同的质数计算方法
 */
public class Sushu {
    public static void main(String[] args) {
        try {
            System.out.println(bf(100));
            System.out.println(eratosthenes(100));
        } catch (IllegalArgumentException e) {
            System.err.println("Error: " + e.getMessage());
        }
    }

    /**
     * 使用暴力方法计算小于 n 的质数数量
     *
     * @param n 需要计算质数的上限
     * @return 小于 n 的质数数量
     * @throws IllegalArgumentException 如果 n 为负数
     */
    public static int bf(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Input must be a non-negative integer. Negative numbers are not valid for prime number calculations.");
        }
        if (n <= 2) {
            return Math.max(0, n - 2); // 当 n <= 2 时，质数个数为 0 或 1
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime(i)) {
                count++;
            }
        }
        return count;
    }

    /**
     * 判断一个数是否为质数
     *
     * @param x 需要判断的数
     * @return 如果 x 是质数返回 true，否则返回 false
     */
    private static boolean isPrime(int x) {
        if (x < 2) {
            return false;
        }
        if (x == 2) {
            return true;
        }
        if (x % 2 == 0) {
            return false;
        }
        int sqrt = (int) Math.sqrt(x);
        for (int i = 3; i <= sqrt; i += 2) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 使用埃拉托斯特尼筛法计算小于 n 的质数数量
     *
     * @param n 需要计算质数的上限
     * @return 小于 n 的质数数量
     * @throws IllegalArgumentException 如果 n 为负数
     */
    public static int eratosthenes(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Input must be a non-negative integer. Negative numbers are not valid for prime number calculations.");
        }
        if (n <= 2) {
            return Math.max(0, n - 2); // 当 n <= 2 时，质数个数为 0 或 1
        }
        // 使用 BitSet 存储是否为质数的信息
        BitSet isPrime = new BitSet(n);
        isPrime.set(2, n);
        int count = 0;
        for (int i = 2; (long) i * i < n; i++) { // 使用 long 类型避免溢出
            if (isPrime.get(i)) {
                count++;
                // 从 i * i 开始标记非质数
                for (int j = i * i; j < n; j += i) {
                    isPrime.set(j, false);
                }
            }
        }
        // 处理 i * i >= n 的情况，只检查奇数
        for (int i = (int) Math.sqrt(n) + 1; i < n; i += 2) {
            if (isPrime.get(i)) {
                count++;
            }
        }
        return count;
    }
}
